#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class MedianFinder {
public:
    MedianFinder() {
        
    }

    void addNum(int num) {
        if (minVal.size() == maxVal.size()) {
            if (minVal.size() == 0 && maxVal.size() == 0) {
                minVal.push(num);
                return;
            }

            if (num < maxVal.top()) {
                minVal.push(num);
            }
            else {
                maxVal.push(num);
            }

        }
        else if (minVal.size() > maxVal.size()) {
            if (maxVal.size() == 0) {
                if (num >= minVal.top()) {
                    maxVal.push(num);
                }
                else {
                    maxVal.push(minVal.top());
                    minVal.pop();
                    minVal.push(num);
                }
                return;
            }


            if (num >= minVal.top()) {
                maxVal.push(num);
            }
            else {
                maxVal.push(minVal.top());
                minVal.pop();
                minVal.push(num);
            }

        }
        else {
            if (num <= maxVal.top()) {
                minVal.push(num);
            }
            else {
                minVal.push(maxVal.top());
                maxVal.pop();
                maxVal.push(num);
            }
        }
    }

    double findMedian() {
        if (minVal.size() == maxVal.size()) {
            return (maxVal.top() + minVal.top()) / 2;
        }
        else {
            return (minVal.size() > maxVal.size()) ? minVal.top() : maxVal.top();
        }
    }
    priority_queue<double> minVal;
    priority_queue<double, vector<double>, greater<double>> maxVal;
    


};